Search for: All records

Abstract A fundamental problem in Ramsey theory is to determine the growth rate in terms of $$n$$ of the Ramsey number $$r(H, K_{n}^{(3)})$$ of a fixed $$3$$-uniform hypergraph $$H$$ versus the complete $$3$$-uniform hypergraph with $$n$$ vertices. We study this problem, proving two main results. First, we show that for a broad class of $$H$$, including links of odd cycles and tight cycles of length not divisible by three, $$r(H, K_{n}^{(3)}) \ge 2^{\Omega _{H}(n \log n)}$$. This significantly generalizes and simplifies an earlier construction of Fox and He which handled the case of links of odd cycles and is sharp both in this case and for all but finitely many tight cycles of length not divisible by three. Second, disproving a folklore conjecture in the area, we show that there exists a linear hypergraph $$H$$ for which $$r(H, K_{n}^{(3)})$$ is superpolynomial in $$n$$. This provides the first example of a separation between $$r(H,K_{n}^{(3)})$$ and $$r(H,K_{n,n,n}^{(3)})$$, since the latter is known to be polynomial in $$n$$ when $$H$$ is linear. 

A group of players are supposed to follow a prescribed profile of strategies. If they follow this profile, they will reach a given target. We show that if the target is not reached because some player deviates, then an outside observer can identify the deviator. We also construct identification methods in two nontrivial cases. 

Abstract We elucidate the relationship between the threshold and the expectation‐threshold of a down‐set. Qualitatively, our main result demonstrates that there exist down‐sets with polynomial gaps between their thresholds and expectation‐thresholds; in particular, the logarithmic gap predictions of Kahn–Kalai and Talagrand (recently proved by Park–Pham and Frankston–Kahn–Narayanan–Park) about up‐sets do not apply to down‐sets. Quantitatively, we show that any collection of graphs on that covers the family of all triangle‐free graphs on satisfies the inequality for some universal , and this is essentially best‐possible. 

Abstract A family of sets is said to be an antichain if for all distinct , and it is said to be a distance‐ code if every pair of distinct elements of has Hamming distance at least . Here, we prove that if is both an antichain and a distance‐ code, then . This result, which is best‐possible up to the implied constant, is a purely combinatorial strengthening of a number of results in Littlewood–Offord theory; for example, our result gives a short combinatorial proof of Hálasz's theorem, while all previously known proofs of this result are Fourier‐analytic.